#include "util.h"
#include "common_sort.h"
#include <algorithm>

/*
https://www.geeksforgeeks.org/radix-sort/

The idea of Radix Sort is to do digit by digit sort starting from 
least significant digit to most significant digit.

Radix Sort uses counting sort as subroutine to sort.

*/

void RadixSort::sort(std::vector<int>& vec) {
	// find the maximum number to know number of digits
	int m = *std::max_element(vec.begin(), vec.end());

	// do counting sort for every digit. Note that instead of passing digit number
	// exp is passed, exp is 10^i where i is current digit number
	for (int exp = 1; m / exp > 0; exp *= 10) {
		countSort(vec, exp);
	}
}

void RadixSort::countSort(std::vector<int>& vec, int exp) {
	int sz = vec.size();

	std::vector<int> output;
	output.resize(sz);

	int count[10] = {0};
	
	// store count of occurrents in count[]
	for (int i = 0; i < sz; ++i) {
		count[(vec[i] / exp) % 10]++;
	}

	// change count[i] so that count[i] now contains actual
	// position of this digit in output[]
	for (int i = 1; i < 10; ++i) {
		count[i] += count[i - 1];
	}

	for (int i = sz - 1; i >= 0; --i) {
		output[count[(vec[i] / exp) % 10] - 1] = vec[i];
		--count[(vec[i] / exp) % 10];
	}

	for (int i = 0; i < sz; ++i) {
		vec[i] = output[i];
	}
}

